package com.mdnote.structure.sort;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/9 21:23
 * @Email rhythm_2019@163.com
 * @Description 复习堆排序
 */
public class HeapSort {

    public static void sort(int[] nums) {

        // 构建大顶堆
        int len = nums.length;

        buildHeap(nums, len);

        for (int i = len - 1; i >= 0; i--) {
            // 取出堆顶元素
            swap(nums, 0, i);
            // 去掉最大元素
            len--;
            // 重新堆顶
            heapify(nums, 0, len);
        }

    }

    // 构建最简大顶堆
    private static void buildHeap(int[] nums, int len) {
        // 最后一个非叶子结点是(nums.length >> 1) - 1
        for (int i = (nums.length >> 1) - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
    }

    private static void heapify(int[] nums, int nodeIdx, int len) {
        int leftIdx = (nodeIdx << 1) + 1;
        int rightIdx = (nodeIdx << 1) + 2;

        int tmpNodeIdx = nodeIdx;
        // nodeIdx、leftIdx和rightIdx中最大值作为顶部
        if (leftIdx < len && nums[leftIdx] > nums[tmpNodeIdx]) {
            tmpNodeIdx = leftIdx;
        }
        if (rightIdx < len && nums[rightIdx] > nums[tmpNodeIdx]) {
            tmpNodeIdx = rightIdx;
        }

        // 看看是否需要调整
        if (tmpNodeIdx != nodeIdx) {
            swap(nums, tmpNodeIdx, nodeIdx);
            // 影响到子堆
            heapify(nums, tmpNodeIdx, len);
        }
    }

    private static void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    @Test
    public void test_01() {
        int[] nums = {11, 33, 44, 2, 22, 7, 9};
        HeapSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
